Modeling objects with smooth surfaces is a central problem in computer graphics, computer aided design (CAD) and computer animation. Moreover, many objects of interest are piecewise smooth, that is their surfaces consist of smoothly curved regions that meet along sharp curves and at sharp corners. Modeling such objects as piecewise linear surfaces, i.e., as a polygon mesh, requires a large number of polygons.
Curved surface models can provide both a more accurate and a more compact representation of the true (or desired) surface. The most popular smooth surface representations are tensor product NURBS (non-uniform rational B-splines). NURBS, however, have two major shortcomings. First because NURBS require a local two dimensional surface parameterization, they can only represent surfaces of arbitrary topology by partitioning the model into a collection of individual NURBS patches. Adjacent patches must then be explicitly stitched together using geometric continuity conditions. See, e.g., G. Farin. Curves and Surfaces for Computer Aided Geometric Design. Academic Press, 3rd edition, 1992. A large number of parameters (the B-spline coefficients) are introduced only to be constrained by the patch continuity conditions, with the result that fitting NURBS to all but topologically flat surfaces requires high-dimensional constrained optimization. These patch constraints are particularly cumbersome in computer animation, where the positions of the B-spline control points are manipulated by the animator who must insure that the continuity conditions are met for each position of the model.
The second problem with NURBS is that they are not capable of explicitly modeling sharp features found in piecewise smooth surfaces. Using everywhere smooth surface elements like NURBS to model such sharp features requires a large number of surface elements to achieve a decent geometric fit.
Subdivision surfaces provide a means for modeling objects of arbitrary topology that include both smooth curved surfaces and sharp edges, thus avoiding both of the shortcomings of NURBS. In 1974 Chaikin introduced the idea of generating a smooth curve from a polygon by successively refining the polygon with the successive addition of new vertices and edges. In 1978, Catmull and Clark and Doo and Sabin extended the idea to surfaces. See E. Catmull and J. Clark. Recursively generated B-Spline surfaces on arbitrary topological meshes. Computer Aided Design, 10(6):350-355, 1978; D. Doo and M. Sabin. Behavior of recursive division surfaces near extraordinary points. Computer Aided Design, 10(6): 356-360, 1978. Subdivision surfaces are constructed beginning with an initial control mesh of arbitrary topology which is refined by adding new vertices, faces and edges at each subdivision step. In the limit of infinite subdivision, the mesh converges to a smooth limiting surface. With particular choices of subdivision rules by which the positions of new vertices, edge, and face points are determined, it can be shown that the limit surface exists, is continuous, and possesses a continuous tangent plane. In particular, Catmull-Clark subdivision leads to limit surfaces which are locally bicubic B-splines except in the neighborhoods of a finite number of exceptional points of the first subdivided mesh at which other then four edges come together. Such exceptional points exist in quadrilateral meshes that model surfaces which are not topologically flat.
Subdivision thus allows for the construction of surfaces of arbitrary topology which locally look like NURBS, but which do not require the use of separate patches or the enforcement of continuity conditions. Moreover, though no closed form expression exists for the limit surface in terms of the original mesh points, the position of points and tangent vectors on the limit surface can be explicitly calculated. The absence of a closed form expression is, therefore, no hindrance to the use of such surfaces in computer graphics or animation. One need only explicitly subdivide the initial mesh until the face size is sufficiently small (i.e., a fraction of a pixel in the rendered scene) and then push the vertex points to their limit positions. One can then calculate the normal vectors to the limit surface at any desire number of points for use in rendering and Phong shading the modeled object.
The incorporation of sharp features, edges, creases, and corners, can also be easily incorporated in models using subdivision surfaces by altering the subdivision rules in the region of such features. See Hoppe, et al., Piecewise Smooth Surface Reconstruction, Computer Graphics (SIGGRAPH '94 Proceedings), pgs. 295-302. Moreover, the present inventors have extended this work to allow for the efficient modeling of semi-sharp features as well. That work is described and claimed in a copending application assigned to the same assignee entitled Hybrid Subdivision in Computer Graphics.
Despite these advantages for modeling piecewise smooth surfaces of arbitrary topology, subdivision surfaces have not been widely adopted in CAD, computer graphics or computer generated animation. One reason that they have not been more widely embraced is that unlike NURB patches, surfaces defined by subdivision do not come with an intrinsic local parametrization. This lack of a parameterization was seen as a major hindrance to the use of subdivision surfaces in computer graphics, because it was thought to prohibit the use of surface or texture maps or other parametric shading techniques. Accordingly, there is a need in computer graphics and animation for a way to define smoothly varying scalar fields on arbitrary polygonal meshes and surfaces defined by their subdivision which can serve as local surface parameters.